#include <iostream>
#include <cassert>
using namespace std;

class UnionFind {

private:
    int *arr;  //存储元素的数组，下标标识其值，数组值为该值的根节点
    int count; //数组大小

public:

    //初始化并查集
    UnionFind(int count) {
        this->count = count;
        arr = new int[count];

        //将每个节点的根设置为自己，标识其没有根节点，自己就是根
        for (int i = 0; i < count; ++i) {
            arr[i] = i;
        }
    }

    //析构函数
    ~UnionFind() {
        delete[] arr;
    }

    //查找x的根节点
    int find(int x) {
        //断言 x 是否越界
        assert(x >= 0 && x < count);

        //规定的数组值就是其 根节点的下标
        return arr[x];
    }

    //联合x,y
    void unionElements(int x, int y) {

        //找出需要联合的两个节点的根节点
        int xRoot = find(x);
        int yRoot = find(y);

        //x , y 就是联合的
        if (xRoot == yRoot) {
            return;
        }

        //将与x的所有相同根节点的根节点更新成yRoot
        for (int i = 0; i < count; ++i) {
            if (arr[i] == xRoot) {
                arr[i] = yRoot;
            }
        }
    }

    //判断两个节点是否有关联
    bool isConnection(int x, int y) {
        return find(x) == find(y);
    }

};

int main() {
    //数据量
    int n = 100000;

    srand(time(NULL));

    UnionFind unionFind = UnionFind(n);

    clock_t startTime = clock(); //时钟周期数
    //随机挑选n对数据进行联合
    for (int i = 0; i < n; i++) {
        int x = rand() % n;
        int y = rand() % n;
        unionFind.unionElements(x, y);
    }

    //随机挑选n对数据进行联系判断
    for (int j = 0; j < n; ++j) {
        int x = rand() % n;
        int y = rand() % n;
        unionFind.isConnection(x, y);
    }
    clock_t endTime = clock();

    cout<< 2*n << " ops " << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;

    return 0;
}